<?php
// 算法记录
// 两数之和
    // 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
    // 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
    // 示例:
    //     给定 nums = [2, 7, 11, 15], target = 9
    //     因为 nums[0] + nums[1] = 2 + 7 = 9
    //     所以返回 [0, 1]

    // 暴力解法
    function twoSum($nums,$target) {
        $count = count($nums);
        for($i = 0;$i < $count; $i++){
            for($j = $i+1; $j<$count; $j++){
                if(($nums[$i]+$nums[$j]) == $target){
                    return [$i,$j];
                }
            }
        }
    }
    // 遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素
    // 时间复杂度 O(n^2)
    // 空间复杂度 O(1)

    // 一次哈希表解法
    function twoSum_hash(array $nums,int $target){
        $map = [];
        foreach($nums as $key => $value){
            $num = $target - $value;
            if(array_key_exists($num,$map) && $key != $map[$num]){
                return [$map[$num],$key];
            }
            $map[$value] = $key;
        }
    }
    // 在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回
    // 时间复杂度 O(n)
    // 空间复杂度 O(n)

// 两数相加
    // 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
    // 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    // 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    // 示例：
    //     输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    //     输出：7 -> 0 -> 8
    //     原因：342 + 465 = 807

    // $array1 = [2,5,6];
    // $array2 = [5,6,4];
    // $l1 = ArrayToListNode($array1);
    // $l2 = ArrayToListNode($array2);
    // $list = addTwoNumbers($l1, $l2);
    // $list = ListNodeToArray($list);

    // 链表对象
    class ListNode {
        public $val = 0;
        public $next = null;
        function __construct($val) { $this->val = $val; }
    }
    // 数组转链表
    function ArrayToListNode($array){
        $max = count($array)-1;
        $list = new ListNode(0);
        $l = $list;
        foreach($array as $key => $value){
            $l->val = $value;
            if($key == $max)
                break;
            $l->next = new ListNode(0);
            $l = $l->next;
        }
        return $list;
    }
    // 链表转数组
    function ListNodeToArray($listNode){
        $array = array();
        $t = $listNode;
        do{
            $array[] = $t->val;
            $t = $t->next;
        }while($t);
        return $array;
    }
    // 链表顺序相加
    function addTwoNumbers($l1, $l2) {
        $l1l = $l1; $l2l = $l2;
        $list = new ListNode(0);
        $l = $list;
        $carry = 0;
        while($l1l != null || $l2l != null){
            $x = ($l1l != null)? $l1l->val : 0;
            $y = ($l2l != null)? $l2l->val : 0;
            $sum = $x + $y + $carry;
            $carry = (int)($sum / 10);
            $l->next = new ListNode($sum % 10);
            $l = $l->next;
            if($l1l != null)
                $l1l = $l1l->next;
            if($l2l != null)
                $l2l = $l2l->next;
        }
        if($carry > 0){
            $l->next = new ListNode($carry);
        }
        return $list->next;
    }
    // 伪代码
        // 将当前结点初始化为返回列表的哑结点。
        // 将进位 carry 初始化为 0。
        // 将 p 和 q 分别初始化为列表 l1 和 l2 的头部。
        // 遍历列表 l1 和 l2 直至到达它们的尾端。
            // 将 x 设为结点 p 的值。如果 p 已经到达 l1 的末尾，则将其值设置为 0。
            // 将 y 设为结点 q 的值。如果 q 已经到达 l2 的末尾，则将其值设置为 0。
            // 设定 sum=x+y+carry。
            // 更新进位的值，carry=sum/10。
            // 创建一个数值为 (summod10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
            // 同时，将 p 和 q 前进到下一个结点。
        // 检查 carry=1 是否成立，如果成立，则向返回列表追加一个含有数字 1 的新结点。
        // 返回哑结点的下一个结点。
    // 时间复杂度 O(max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m, n) 次
    // 空间复杂度 O(max(m,n))， 新列表的长度最多为 max(m,n)+1

// 无重复字符串的最长子串
    // 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
    // 示例 1:
        // 输入: "abcabcbb"
        // 输出: 3 
        // 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    // 示例 2:
        // 输入: "bbbbb"
        // 输出: 1
        // 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    // 示例 3:
        // 输入: "pwwkew"
        // 输出: 3
        // 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
        //     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

    // 滑动窗口+哈希
    function lengthOfLongestSubstring($s) {
        $strlen = strlen($s);
        $maxstr = array();
        $length = 0;
        $result = 0;
        $start = 0;

        for($i=0; $i<$strlen; $i++){
            if(isset($maxstr[$s[$i]]) && $maxstr[$s[$i]] >= $start){
                if($length > $result){
                    $result = $length;
                }
                $start = $maxstr[$s[$i]] + 1;
                $length = $i - $start;
            }
            $maxstr[$s[$i]] = $i;
            $length++;
        }
        return max($result,$length);
    }

    // 滑动窗口+hash，两个指针，一个指向起始，一个向后遍历，遇到重复起始指针指向出现重复位置+1，此时长度为后指针减前指针，记录最大不重复长度
    // 时间复杂度 O(n)，索引 i 将会迭代 n 次
    // 空间复杂度 O(m)，m 是字符集的大小

// 寻找两个有序数组的中位数
    // 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2
    // 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))
    // 你可以假设 nums1 和 nums2 不会同时为空
    // 示例 1:
        // $nums1 = [1, 3];
        // $nums2 = [2];
        // 则中位数是 2.0
    // 示例 2:
        // $nums1 = [1, 3];
        // $nums2 = [2, 4];
        // 则中位数是 (2 + 3)/2 = 2.5

    // 二分法
    function findMedianSortedArrays($nums1, $nums2) {
        $m = count($nums1);
        $n = count($nums2);

        if($m > $n){
            $temp = $nums1; $nums1 = $nums2; $nums2 = $temp;
            $tmp = $m; $m = $n; $n = $tmp;
        }

        $iMin = 0; $iMax = $m; $halfLen = (int)(($m + $n +1) /2);
        while($iMin <= $iMax){
            $i = (int)(($iMin + $iMax) /2);
            $j = $halfLen - $i;
            if($i < $iMax && $nums2[$j-1] > $nums1[$i]){
                $iMin = $i +1;
            }else if($i > $iMin && $nums1[$i -1] > $nums2[$j]){
                $iMax = $i -1;
            }else{
                $maxLeft = 0;
                if($i == 0)
                    $maxLeft = $nums2[$j -1];
                else if($j == 0)
                    $maxLeft = $nums1[$i -1];
                else
                    $maxLeft = max($nums1[$i -1],$nums2[$j -1]);
                if(($m + $n)%2 == 1)
                    return $maxLeft;

                $minRight = 0;
                if($i == $m)
                    $minRight = $nums2[$j];
                else if($j == $n)
                    $minRight = $nums1[$i];
                else
                    $minRight = min($nums2[$j],$nums1[$i]);
                return ($maxLeft + $minRight) /2.0;
            }
        }
        return 0.0;
    }

    // 解释
        // 首先，让我们在任一位置 i 将 A 划分成两个部分
        //         left_A               |      right_A
        //     A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
        // 由于 A 中有 m 个元素， 所以我们有 m+1 种划分的方法（i = 0 ~ m）
        //     len(left_A)=i,len(right_A)=m−i
        //     注意：当 i=0 时，left_A 为空集， 而当 i=m 时, right_A 为空集。
        // 采用同样的方式，我们在任一位置 j 将 B 划分成两个部分
        // 将 left_A 和 left_B 放入一个集合，并将 right_A 和 right_B 放入另一个集合。 
        // 再把这两个新的集合分别命名为 left_part 和 right_part
        //         left_part            |      right_part
        //     A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
        //     B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
        // 如果我们可以确认
        //     len(left_part)=len(right_part)
        //     max(left_part)≤min(right_part)
        // 我们已经将 {A,B} 中的所有元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素
        //     median= (max(left_part)+min(right_part))/2
        // 要确保这两个条件，我们只需要保证
        //     i+j=m−i+n−j（或：m−i+n−j+1） 如果 n≥m，只需要使  i=0~m，j=(m+n+1)/2-i
        //     B[j−1]≤A[i] 以及 A[i−1]≤B[j]

        // 在 [0，m] 中搜索并找到目标对象 i，以使
        //     B[j−1]≤A[i]且A[i−1]≤B[j]，其中j=(m+n+1)/2-i
        // 接着，我们可以按照以下步骤来进行二叉树搜索
        //     1.设 imin=0，imax=m, 然后开始在 [imin,imax] 中进行搜索
        //     2.令i=(imin+imax)/2,j=(m+n+1)/2-i
        //     3.现在我们有 len(left_part)=len(right_part)。 而且我们只会遇到三种情况
        //         B[j−1]≤A[i]且A[i−1]≤B[j]
        //             这意味着我们找到了目标对象 i，所以可以停止搜索
        //         B[j−1]>A[i]
        //             这意味着 A[i] 太小，我们必须调整 i 以使 B[j−1]≤A[i]
        //             因为当 i 被增大的时候，j 就会被减小
        //             因此 B[j−1] 会减小，而 A[i] 会增大，那么B[j−1]≤A[i] 就可能被满足
        //             我们必须将搜索范围调整为 [i+1,imax]
        //             因此，设 imin=i+1，并转到步骤 2
        //         A[i−1]>B[j]
        //             这意味着 A[i−1] 太大，我们必须减小 i 以使 [j]A[i−1]≤B[j]
        //             我们必须将搜索范围调整为 [imin,i−1]
        //             因此，设 imax=i−1，并转到步骤 2
        //     当找到目标对象 i 时，中位数为
        //         max(A[i−1],B[j−1]), 当 m+n 为奇数时
        //         (max(A[i−1],B[j−1])+min(A[i],B[j]))/2, 当m+n 为偶数时

        // 让我们来考虑这些临界值 i=0,i=m,j=0,j=n，此时 A[i−1],B[j−1],A[i],B[j] 可能不存在
        //     我们需要做的是确保 max(left_part)≤min(right_part)
        //     如果 i 和 j 不是临界值（这意味着 A[i−1],B[j−1],A[i],B[j] 全部存在）, 那么我们必须同时检查 B[j−1]≤A[i] 以及 A[i−1]≤B[j] 是否成立
        //     但是如果 A[i−1],B[j−1],A[i],B[j] 中部分不存在，那么我们只需要检查这两个条件中的一个（或不需要检查）
        //     所以，我们需要做的是
        //         在 [0，m] 中搜索并找到目标对象 i，以使
        //         (j=0 or i=m or B[j−1]≤A[i]) 或是 (i=0 orj=n or A[i−1]≤B[j]), 其中j=(m+n+1)/2-i
        //     在循环搜索中，我们只会遇到三种情况
        //         (j=0 or i=m or B[j−1]≤A[i]) 或是 (i=0 or j=n or A[i−1]≤B[j])，这意味着 i 是完美的，我们可以停止搜索
        //         i<m and B[j−1]>A[i] 这意味着 i 太小，我们必须增大它
        //         i>0 and A[i−1]>B[j] 这意味着 i 太大，我们必须减小它

    // 时间复杂度 O(log(min(m,n)))
        // 查找的区间是 [0, m]。 而该区间的长度在每次循环之后都会减少为原来的一半。 
        // 我们只需要执行 log(m) 次循环。由于我们在每次循环中进行常量次数的操作，所以时间复杂度为 O(log(m))。
        // 由于 m≤n，所以时间复杂度是 O(log(min(m,n)))
    // 空间复杂度 O(1)， 我们只需要恒定的内存来存储 9 个局部变量， 所以空间复杂度为 O(1)

// 最长回文子串
    // 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    // 示例 1：
        // 输入: "babad"
        // 输出: "bab"
        // 注意: "aba" 也是一个有效答案。
    // 示例 2：
        // 输入: "cbbd"
        // 输出: "bb"

    // 中心扩展
    function longestPalindrome($s) {
        $strlen = strlen($s);
        if($strlen < 1)
            return "";
        else if($strlen == 1)
            return $s;
        else if($strlen == 2)
            return $s[0] == $s[1] ? $s : $s[0];
        $start = 0;
        $end = 0;
        for($i = 0; $i < $strlen; $i++){
            $len1 = expandAroundCenter($s, $i, $i, $strlen); // 奇数回文
            $len2 = expandAroundCenter($s, $i, $i + 1, $strlen); //偶数回文
            
            $len = max($len1,$len2);
            if($len > $end - $start ){
                $start = $i - (int)(($len - 1 )/2);
                $end = $i + (int)($len/2);
            }
        }
        return substr($s, $start, $end + 1 - $start);
    }

    function expandAroundCenter($s, $left, $right, $strlen){
        while($left >= 0 && $right < $strlen && $s[$left] == $s[$right]){
            $left--;
            $right++;
        }
        return $right - $left -1;
    }

    // 回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心
    // 所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个 ‘b’ 之间）
    // 时间复杂度 O(n^2)，由于围绕中心来扩展回文会耗去 O(n) 的时间，所以总的复杂度为 O(n^2)
    // 空间复杂度 O(1)

    // Manacher算法 马拉车算法
    function longestPalindromeManacher($s){
        $s_len = strlen($s);
        $s_new = '$#';
        $len = 2;
        for($i = 0; $i < $s_len; $i++){
            $s_new[$len++] = $s[$i];
            $s_new[$len++] = '#';
        }
        $max_len = -1;
        $max_i = -1;
        $id = 0;
        $mx = 0;

        for($i = 1; $i < $len; $i++){
            if($i < $mx)
                $p[$i] = min($p[ 2*$id-$i ], $mx-$i);
            else
                $p[$i] =1;
            while( ($i+$p[$i] < $len) && ($s_new[$i-$p[$i]] == $s_new[$i+$p[$i]]) )
                $p[$i]++;
            if( $mx < $i+$p[$i] ){
                $id = $i;
                $mx = $i + $p[$i];
            }
            if($p[$i]-1 > $max_len){
                $max_len = $p[$i]-1;
                $max_i = $i;
            }
        }
        return str_replace('#', '', substr($s_new, $max_i - $max_len, $max_len*2));
    }

    // 解释
        // 字符串插空法插入字符串中不存在的字符当做分隔符，在首字符插入字符防止越界。转换成奇回文问题
        // 从左到右遍历字符串，记录个字符串的最长回文长度，记录回文右边界
    // 时间复杂度 O(n)
    // 空间复杂度 O(n)